package cc.wsyw126.java.nowcoder;

/**
 * Created by Administrator on 2017/4/12.
 */
public class P01 {
    public int getMaxValue(int mw, int[] w, int[] v) {
        int[][] mark = new int[w.length+1][mw + 1];
        for (int i = 0; i < w.length; i++) {
            for (int j = 1; j <= mw; j++) {
                if (j >= w[i]) {
                    int value = mark[i][j - w[i]] + v[i];
                    if (value > mark[i][j]) {
                        mark[i+1][j] = value;
                    } else {
                        mark[i+1][j] = mark[i][j];
                    }
                }else {
                    mark[i+1][j] = mark[i][j];
                }
            }
        }
        return mark[w.length][mw];
    }

    public static void main(String[] args) {
        int[] w = {1,2,3,4,5};
        int[] v = {1,4,2,5,6};
        int mw = 3;
        P01 p01 = new P01();
        int maxValue = p01.getMaxValue(mw, w, v);
        System.out.println("maxValue = " + maxValue);
    }
}
